// 定义红黑树节点类
class TreeNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
    this.parent = null;
    this.color = 'RED'; // 新节点默认为红色
  }
}

// 定义红黑树类
class RedBlackTree {
  constructor() {
    this.root = null;
  }

  // 左旋操作
  leftRotate(x) {
    let y = x.right;
    x.right = y.left;
    if (y.left !== null) {
      y.left.parent = x;
    }
    y.parent = x.parent;
    if (x.parent === null) {
      this.root = y;
    } else if (x === x.parent.left) {
      x.parent.left = y;
    } else {
      x.parent.right = y;
    }
    y.left = x;
    x.parent = y;
  }

  // 右旋操作
  rightRotate(y) {
    let x = y.left;
    y.left = x.right;
    if (x.right !== null) {
      x.right.parent = y;
    }
    x.parent = y.parent;
    if (y.parent === null) {
      this.root = x;
    } else if (y === y.parent.right) {
      y.parent.right = x;
    } else {
      y.parent.left = x;
    }
    x.right = y;
    y.parent = x;
  }

  // 插入修复操作
  insertFixup(z) {
    while (z.parent && z.parent.color === 'RED') {
      if (z.parent === z.parent.parent.left) {
        let y = z.parent.parent.right;
        if (y && y.color === 'RED') {
          z.parent.color = 'BLACK';
          y.color = 'BLACK';
          z.parent.parent.color = 'RED';
          z = z.parent.parent;
        } else {
          if (z === z.parent.right) {
            z = z.parent;
            this.leftRotate(z);
          }
          z.parent.color = 'BLACK';
          z.parent.parent.color = 'RED';
          this.rightRotate(z.parent.parent);
        }
      } else {
        let y = z.parent.parent.left;
        if (y && y.color === 'RED') {
          z.parent.color = 'BLACK';
          y.color = 'BLACK';
          z.parent.parent.color = 'RED';
          z = z.parent.parent;
        } else {
          if (z === z.parent.left) {
            z = z.parent;
            this.rightRotate(z);
          }
          z.parent.color = 'BLACK';
          z.parent.parent.color = 'RED';
          this.leftRotate(z.parent.parent);
        }
      }
    }
    this.root.color = 'BLACK';
  }

  // 插入节点操作
  insert(key, value) {
    let z = new TreeNode(key, value);
    let y = null;
    let x = this.root;

    while (x !== null) {
      y = x;
      if (z.key < x.key) {
        x = x.left;
      } else {
        x = x.right;
      }
    }

    z.parent = y;
    if (y === null) {
      this.root = z;
    } else if (z.key < y.key) {
      y.left = z;
    } else {
      y.right = z;
    }

    this.insertFixup(z);
  }

  // 查找节点操作
  search(key) {
    let x = this.root;
    while (x !== null) {
      if (key === x.key) {
        return x.value;
      } else if (key < x.key) {
        x = x.left;
      } else {
        x = x.right;
      }
    }
    return null;
  }
}

// 使用示例
let rbTree = new RedBlackTree();
rbTree.insert(10, 'Value 10');
rbTree.insert(20, 'Value 20');
rbTree.insert(30, 'Value 30');
console.log(rbTree.search(20)); // 输出: Value 20
